浅谈分块

分块,就是一种优雅的暴力。它可以将 O(n2)O(n^2) 的暴力变成 O(nn)O(n \sqrt{n})

一、如何实现分块

如图:

实现:

int n, T; scanf("%d%d", &n, &T);
for (int i = 1; i <= n; i++) scanf("%lld", A + i); // 数组
t = sqrt(n); // 块长
for (int i = 1; i <= t; i++) {
    L[i] = (i - 1) * t + 1;
    R[i] = i * t;
} // L 表示块的左边界, R表示块的右边界
if (R[t] < n) L[t + 1] = t * t + 1, R[++t] = n;
for (int i = 1; i <= t; i++) {
    for (int j = L[i]; j <= R[i]; j++) {
        pos[j] = i; // pos[j]表示第j个数所处的块的位置
        sum[i] += A[j]; // sum[i]表示第i个块的和
    }
}

二、如何实现加法

如果让你在 [l,r][l, r] 之间的每个数都加上 kk ,对块进行如图操作(这里 l=3,r=13l = 3, r = 13):

实现:

void upd(int l, int r, LL val) {
	if (pos[l] == pos[r]) for (int i = l; i <= r; i++) A[i] += val, sum[pos[l]] += val;
	else {
		for (int i = l; i <= R[pos[l]]; i++) A[i] += val, sum[pos[l]] += val;
		for (int i = L[pos[r]]; i <= r; i++) A[i] += val, sum[pos[r]] += val;
		for (int i = pos[l] + 1; i < pos[r]; i++) tag[i] += val;
	}
}

三、如何实现查询

如果让你在 [l,r][l, r] 之间的每个数都加上 kk ,对块进行如图操作(这里 l=6,r=17l = 6, r = 17):

实现:

LL query(int l, int r) {
	LL ret = 0ll;
	if (pos[l] == pos[r]) for (int i = l; i <= r; i++) ret += A[i] + tag[pos[l]];
	else {
		for (int i = l; i <= R[pos[l]]; i++) ret += A[i] + tag[pos[l]];
		for (int i = L[pos[r]]; i <= r; i++) ret += A[i] + tag[pos[r]];
		for (int i = pos[l] + 1; i < pos[r]; i++) ret += sum[i] + (R[i] - L[i] + 1) * tag[i];
	}
	return ret;
}

总体实现(例题 P3372):

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
typedef long long LL;
LL A[N], sum[N], tag[N];
int pos[N], L[N], R[N], t;
void upd(int l, int r, LL val) {
	if (pos[l] == pos[r]) for (int i = l; i <= r; i++) A[i] += val, sum[pos[l]] += val;
	else {
		for (int i = l; i <= R[pos[l]]; i++) A[i] += val, sum[pos[l]] += val;
		for (int i = L[pos[r]]; i <= r; i++) A[i] += val, sum[pos[r]] += val;
		for (int i = pos[l] + 1; i < pos[r]; i++) tag[i] += val;
	}
}
LL query(int l, int r) {
	LL ret = 0ll;
	if (pos[l] == pos[r]) for (int i = l; i <= r; i++) ret += A[i] + tag[pos[l]];
	else {
		for (int i = l; i <= R[pos[l]]; i++) ret += A[i] + tag[pos[l]];
		for (int i = L[pos[r]]; i <= r; i++) ret += A[i] + tag[pos[r]];
		for (int i = pos[l] + 1; i < pos[r]; i++) ret += sum[i] + (R[i] - L[i] + 1) * tag[i];
	}
	return ret;
}
int main() {
	int n, T; scanf("%d%d", &n, &T);
	for (int i = 1; i <= n; i++) scanf("%lld", A + i);
	t = sqrt(n);
	for (int i = 1; i <= t; i++) {
		L[i] = (i - 1) * t + 1;
		R[i] = i * t;
	}
	if (R[t] < n) L[t + 1] = t * t + 1, R[++t] = n;
	for (int i = 1; i <= t; i++) {
		for (int j = L[i]; j <= R[i]; j++) {
			pos[j] = i;
			sum[i] += A[j];
		}
	}
	LL k;
	for (int op, l, r; T--; ) {
		scanf("%d%d%d", &op, &l, &r);
		if (op == 1) scanf("%lld", &k), upd(l, r, k);
		else printf("%lld\n", query(l, r));
	}
	return 0;
}

四、如何插入元素

如果让你在位置 xx 插入一个元素,你可以在每一个块内弄一个双端队列,固定块长,如图(以 x=6x = 6 为例):

88 从第二个块的末尾弹出,进入第三个块的前端,12121616 同理。这里显然不能直接手写 dequedeque ,所以可以用 STLSTL 中的 dequedeque 来实现插入元素和单点查询,复杂度 O(nn)O(n \sqrt{n})(插入 O(n)O(\sqrt{n}) ,从 dequedeque 中暴力查询 O(n)O(\sqrt{n}))。

如果想要手写 dequedeque,可以开一个 22 倍块长的数组,如下表进行操作:

开始时:

1 2 3 4 5 6 7 8
5 6 7 8

11 次:

1 2 3 4 5 6 7 8
4 5 6 7

22 次:

1 2 3 4 5 6 7 8
3 4 5 6

\cdots块长=4=4)次:

1 2 3 4 5 6 7 8
1 2 3 4

当到头了的时候,我们可以将其暴力放到末尾:

1 2 3 4 5 6 7 8
1 2 3 4

一次暴力的复杂度时 O(n)O(\sqrt{n}) ,但这需要 n\sqrt{n} 次操作后才可以进行该操作,所以均摊到每次操作上就是 O(1)O(1) 的。

可以发现,这样做可以将查询的时间复杂度降到 O(1)O(1) ,代码实现:

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
typedef long long LL;
const int Block_Start = 801; // Block_Size = Block_Start
int Size, B[N];
struct per {
	int A[Block_Start << 1 | 5], Al = Block_Start, Ar = Block_Start;
	per() {Al = Ar = Block_Start;}
	void insert(int pos, int val) {
		for (int i = Ar - 1; i >= Al + pos - 1; i--) A[i + 1] = A[i];
		A[Al + pos - 1] = val; Ar++;
	}
	void Move_Back() {
		if (Al > Block_Start - Size) return;
		for (int i = Ar - 1; i >= Al; i--) A[Block_Start - Al + i] = A[i];
		int tsz = Ar - Al;
		Al = Block_Start; Ar = Al + tsz;
	}
	int query(int pos) {
		return A[Al + pos - 1];
	}
}p[505];
LL min(LL x, LL y) {return x < y ? x : y;}
LL max(LL x, LL y) {return x > y ? x : y;}
void Roll_To_Next_Block(int Block) {
	while (p[Block].Ar - p[Block].Al > Size) {
		p[Block + 1].A[--p[Block + 1].Al] = p[Block].A[--p[Block].Ar];
		p[Block + 1].Move_Back();
		Block++;
	}
}
void upd(int pos, int val) {
	int Block = (pos - 1) / Size + 1;
	p[Block].insert(pos - (Block - 1) * Size, val);
	Roll_To_Next_Block(Block);
}
int query(int pos) {
	int Block = (pos - 1) / Size + 1;
	return p[Block].query(pos - (Block - 1) * Size);
}
int main() {
    srand((unsigned)time(0));
	int n, T; scanf("%d", &n); T = n;
	for (int i = 1; i <= n; i++) scanf("%d", B + i);
	Size = sqrt(n * 2.5);
	for (int i = 1, Block; i <= n; i++) {
		Block = (i - 1) / Size + 1;
		p[Block].insert(i - (Block - 1) * Size, B[i]);
	}
	int tot = n;
	for (int op, l, r, k; T--; ) {
		scanf("%d%d%d%d", &op, &l, &r, &k);
		if (op == 0) upd(l, r);
		else printf("%d\n", query(r));
	}
	return 0;
}

感谢观看!